<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<section>
    <h4>二叉树</h4>
    <ul>
        <li>普通二叉树</li>
        <li>有序二叉树</li>
    </ul>
</section>
<script>
    // 普通二叉树
    class BinaryTree {
        root = null

        // 添加
        add(node) {
            let _node = {
                value: node,
                left: null,
                right: null
            }

            if (!this.root) {
                this.root = _node
                return
            }
            let _root = this.root

            while(_root) {
                // 判断左节点是否存在
                if (!_root.left) {
                    _root.left = _node
                    break
                }
                // 判断右节点是否存在
                else if (!_root.right) {
                    _root.right = _node
                    break
                }
                // 判断两个节点是否都存在
                else if (_root.left && _root.right) {
                    // 进入下次循环
                    if (!_root.left.left || !_root.left.right) {
                        _root = _root.left
                    } else {
                        _root = _root.right
                    }
                }
            }
        }

        // 批量添加
        patchAdd(arr = []) {
            arr.forEach((item) => {
                this.add(item)
            })
        }

        // 先序遍历(根左右)
        rootLeftRight(root) {
            if (root) {
                console.log(root.value)
                this.rootLeftRight(root.left)
                this.rootLeftRight(root.right)
            }
        }

        // 中序遍历(左根右)
        leftRootRight(root) {
            if (root) {
                this.leftRootRight(root.left)
                console.log(root.value)
                this.leftRootRight(root.right)
            }
        }

        // 后序遍历(左右根)
        leftRightRoot(root) {
            if (root) {
                this.leftRightRoot(root.left)
                this.leftRightRoot(root.right)
                console.log(root.value)
            }
        }
    }

    let tree = new BinaryTree()
    tree.patchAdd([1,2,3,4,5,6])
    console.log(tree, tree.root)
    /**
     * 批量添加，就出现如下结构
     *                  1
     *          2               3
     *      4       5       6
     *
     */
    // 先序遍历 预期结果1 2 4 5 3 6
    // tree.rootLeftRight(tree.root)
    // 中序遍历 预期结果4 2 5 1 6 3
    // tree.leftRootRight(tree.root)
    // 后序遍历 预期结果4 5 2 6 3 1
    // tree.leftRightRoot(tree.root)
</script>
<script>
    class OrderedBinaryTree {
        root = null

        // 添加
        add(val) {
            const _node = {
                value: val,
                left: null,
                right: null
            }

            if (!this.root) {
                this.root = _node
                return
            }

            let _root = this.root
            while(_root) {
                // val小于根节点放左边
                if (val < _root.value) {
                    // 左边有值的话，进入下一个循环
                    if (_root.left) {
                        _root = _root.left
                    } else {
                        _root.left = _node
                        break
                    }
                }
                // val大于等于根节点放右边
                else {
                    // 右边有值的话，进入下一个循环
                    if (_root.right) {
                        _root = _root.right
                    } else {
                        _root.right = _node
                        break
                    }
                }
            }
        }

        // 批量添加
        patchAdd(arr = []) {
            arr.forEach((item) => {
                this.add(item)
            })
        }

        // 先序遍历（根左右）
        rootLeftRight(root) {
            if (root) {
                console.log(root.value)
                this.rootLeftRight(root.left)
                this.rootLeftRight(root.right)
            }
        }

        // 中序遍历（左根右）
        leftRootRight(root) {
            if (root) {
                this.leftRootRight(root.left)
                console.log(root.value)
                this.leftRootRight(root.right)
            }
        }

        // 后序遍历（左右根）
        leftRightRoot(root) {
            if (root) {
                this.leftRightRoot(root.left)
                this.leftRightRoot(root.right)
                console.log(root.value)
            }
        }
    }

    let orderedBinaryTree = new OrderedBinaryTree()
    orderedBinaryTree.patchAdd([5,4,6,2,1,3])
    console.log(orderedBinaryTree, orderedBinaryTree.root)
    /**
     * 批量添加，就出现如下结构
     *                  5
     *           4               6
     *      2
     *   1     3
     *
     */
    // 先序遍历 预期结果5 4 2 1 3 6
    // orderedBinaryTree.rootLeftRight(orderedBinaryTree.root)
    // 中序遍历 预期结果1 2 3 4 5 6
    // orderedBinaryTree.leftRootRight(orderedBinaryTree.root)
    // 后序遍历 预期结果1 3 2 4 6 5
    // orderedBinaryTree.leftRightRoot(orderedBinaryTree.root)
</script>
</body>
</html>
